package com.demo.datastructure.binarySearch;

/**
 * @author ljr
 * @version 1.0
 * @description: 查找最后一个大于给定值的元素
 * @date 2021/10/13 17:25
 */
public class BinarySearch17 {

    public static int bsearch(int[] nums, int target) {
        int low = 0, high = nums.length-1, n = high;
        int min = nums[0];
        if(target == min) return 0;
        int max = nums[n];
        if(target == max) return n;
        if(target > max && target < min) return -1;
        //目标值可能在前半段, 也可能在后半段
        while(low <= high) {
            int mid = low + (high - low >> 1);
            if(nums[mid] < target){
                //当中间数小于目标值时, 判断中间值和目标值是否在同一段
                //不会出现target在后半段, mid值在前半段
                //如果target在前半段，mid值在后半段,高位赋值,
                //否则低位赋值
                if(min >= max && target > min && nums[mid] <= max){
                    high = mid - 1;
                }else{
                    low = mid + 1;
                }
            }else if(nums[mid] > target){
                //当中间数大于目标值时, 判断中间值和目标值是否在同一段
                //不会出现target在前端半段, mid值在后半段
                //如果target在后半段，mid值在前半段,低位赋值,
                //否则高位赋值
                if(min >= max && target < max && nums[mid] >= min){
                    low = mid + 1;
                }else{
                    high = mid - 1;
                }
            }else{
                return mid;
            }
        }
        return -1;
    }


    public static int bsearch2(int[] nums, int target) {
        int low = 0, high = nums.length-1, n = high;
        int min = nums[0];
        if(target == min) return 0;
        int max = nums[n];
        if(target == max) return n;
        if(target > max && target < min) return -1;
        //目标值可能在前半段, 也可能在后半段
        while(low <= high) {
            int mid = low + (high - low >> 1);
            if(nums[mid] == target) return mid;
            if(nums[mid] <= max){
                if (target < nums[mid] || target > nums[high]) {
                    high = mid - 1;
                } else low = mid + 1;
            }else{
                if (target < nums[low] || target > nums[mid]) {
                    low = mid + 1;
                } else high = mid - 1;
            }
        }
        return -1;
    }


    public static int bsearch3(int[] nums, int target) {
        int low = 0, high = nums.length-1, n = high;
        int min = nums[0];
        if(target == min) return 0;
        int max = nums[n];
        if(target == max) return n;
        if(target > max && target < min) return -1;

        while(low <= high){
            int mid = low + (high - low >> 1);
            if(nums[mid] == target) return mid;
            if(nums[mid] <= max){
                if(nums[mid] > target || target > nums[high]){
                    high = mid - 1;
                }else low = mid + 1;
            }else{
                if(target < nums[low] || target > nums[mid]){
                    low = mid + 1;
                }else high = mid - 1;
            }
        }
        return -1;
    }

    public static int bsearch4(int[] nums, int target) {
        int s = 0;
        int e = nums.length - 1;
        while (e >= s){
            int mid = s + (e-s)/2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < nums[e]) {
                if (target < nums[mid] || target > nums[e]) {
                    e = mid - 1;
                } else s = mid + 1;
            } else {
                if (target < nums[s] || target > nums[mid]) {
                    s = mid + 1;
                } else e = mid - 1;
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        //int[] nums = new int[]{1,3,5};
        int[] nums = new int[]{4,5,6,7,0,1,2};
        int index = BinarySearch17.bsearch3(nums,0);
        System.out.println(index);
    }

}
